This invention relates to a secret-key enciphering method and an arrangement therefor and, in particular, to a secret-key enciphering method and a secret-key enciphering arrangement which are for use in a communication system or a computer system and which are for transforming original information into a cipher through a predetermined operation and for reversing the cipher into the original information in order to prevent an unauthorized person from unfair acquirement of the information.
In a communication system or a computer system, it is a general practice to transform original information into a cipher through a predetermined operation and to reverse the cipher into the original information in order to prevent an unauthorized person from unfair acquirement of the information. In this specification, a process of transforming the original information into the cipher is called enciphered while a process of reversing the cipher into the original information is called a decipherment. The original information before encipherment is called a plaintext. The cipher obtained by subjecting the information to the encipherment process is called a ciphertext.
As a method of enciphering the information, a linear transformation cipher has widely been used. This cipher transforms an integer expression M of the plaintext into an integer expression C of the ciphertext through a process represented by the following equation. EQU C=aM+b(mod p) (1)
Herein, a, b, and p are predetermined integers and X (mod Y) implies a remainder when X is divided by Y, In the following description, Y in X (mod Y) is called a modulo. The remainder when X is divided by Y is called a residue.
The ciphertext can be reversed into the plaintext through a process represented by the following equation. EQU M=(C-b)/a(mod p) (2)
Herein, a division z=x/y (mod p) implies a calculation of z satisfying x=yz (mod p). A method of calculating the division is described, for example, in a book entitled "Cryptography and Data Security" written by Dorothy Elizabeth Robling Denning, published by Addison-Wesley Publishing Company, Inc., 1982, pp. 43-45.
In the linear transformation cipher, either or a both of a and b are used as a cryptographic key which comprises secret values preliminarily determined by communicators, while a value obtained by adding "1" to the maximum value in the plaintext is selected as p. The linear transformation cipher has been used for a long time because it is easily processed. For example, the linear transformation cipher with a equal to 1 and b used as a cryptographic key has been utilized since the era of Caesar. Explanation of the linear transformation cipher is given, for example, in a book entitled "Introduction to Decipherment by the use of a Computer" written by Kineo Matsui and published by Morikita Publishing Corp., 1990 and in the above-mentioned book entitled "Cryptography and Data Security" written by Denning, pp. 66-67. In the latter reference, the cipher is not called the linear cipher but is referred to as an affine transformation cipher.
In a cipher communication apparatus based on the linear transformation cipher, however, a linear relationship is kept between the plaintext and the ciphertext. If several plaintext-ciphertext pairs are obtained, the cryptographic key can be undesiredly calculated by solving a linear equation.
In view of the above, it has been a practice to repeat linear transformation by the use of different moduli relatively prime to each other. Specifically, it is a general practice to repeat linear transformation m times by the use of different moduli p.sub.i (i=1, 2, . . . , m) relatively prime to each other to transform a plaintext M into a ciphertext C, as represented by the following equations. ##EQU1## By repeating linear transformation by the use of the different moduli relatively prime to each other, nonlinear transformation is achieved. In the following description, the cipher defined by the foregoing equations is called a primitive multiple-modulus cipher.
In the primitive multiple-modulus cipher, it is necessary to select a cryptographic key satisfying p.sub.1 &lt;p.sub.2 &lt; . . . &lt;p.sub.m in order to correctly reverse the plaintext from the ciphertext. Otherwise, for several ciphertexts, a plurality of plaintexts may correspond to one ciphertext. In this connection, the ciphertext inevitably has a bit length longer than that of the plaintext in the primitive multiple-modulus cipher.
However, in data communication and the like, use is generally made of such a cipher that the plaintext of 64 bits are transformed into the ciphertext of 64 bits. Accordingly, the above-mentioned primitive multiple-modulus cipher can not be used in the data communication.
In order to coincide the length of the plaintext and the length of the ciphertext, use has been made of a technique which will presently be described. It is assumed here that a transformation f[a.sub.i, b.sub.i, p.sub.i ] is a process of producing an output a.sub.i x+b.sub.i (mod p.sub.i) when an input x has a value smaller than p.sub.i and of producing an output equivalent to x when the input x is not smaller than p.sub.i while a transformation g is a process of producing an output obtained by inverting a most significant bit of an input. Instead of the linear transformation, a transformation composed of these transformations in the order of f[a.sub.i, b.sub.i, p.sub.i ], g, and f[a.sub.i, b.sub.i, p.sub.i ] is repeatedly carried out. Such transformation composed of f[a.sub.i, b.sub.i, p.sub.i ], g, and f[a.sub.i, b.sub.i, p.sub.i ] in this order is represented by ELT[a.sub.i, b.sub.i, p.sub.i ].
Specifically, the above-mentioned transformation is represented by the following equations. ##EQU2## In this manner, any plaintext of n bits can be transformed into a ciphertext of n bits as far as different n-bit integers relatively prime to each other are selected as p.sub.i (i=1, 2, . . . , m). Herein, a cipher using the enciphering process represented by the above-mentioned equations is called a multiple-modulus cipher.
In order to reverse the ciphertext c of the above-mentioned multiple-modulus cipher into the plaintext M, a process represented by the following equations is carried out. ##EQU3## Herein, a.sub.i ' and b.sub.1 ' are values defined by a.sub.i '=1/a.sub.i (mod p.sub.i) and b.sub.i '=-b.sub.i /a.sub.i (mod p.sub.i), respectively. Accordingly, only by changing variables, both encipherment and decipherment of the multiple-modulus cipher can be carried out by the use of a same arrangement.
Encipherment of the multiple-modulus cipher is generally carried out in the manner described above. In order to improve a scrambling effect, the transformation g may comprise, instead of the process of inverting the most significant bit of the input, a process of inverting the most significant bit and carrying out an exclusive-OR operation between a plurality of high-order bits following the most significant bit and a plurality of bits determined in dependence upon low-order bits than those bits.
In order to improve the scrambling effect, the transformation g may be carried out between a transformation ELT (Expanded Linear Transformation) and another transformation ELT. In this event, encipherment is carried out in accordance with the following equations. ##EQU4## Otherwise, encipherment is carried out in accordance with the following equations. ##EQU5##
The principles of the primitive multiple-modulus cipher and the multiple-modulus cipher described in conjunction with Equations (3) through (7) and the arrangements for executing encipherment and decipherment of these ciphers are described in detail in Japanese Patent Publication (JP-A) No. 75525/1994 (Japanese Patent Application No. 128409/1992) and in U.S. Pat. No. 5,301,235.
However, the multiple-modulus cipher used in the conventional secret-key enciphering method and the arrangement therefor has a disadvantage that the scrambling effect is not sufficient. For example, it is assumed that p.sub.1 and p.sub.2 have values approximate to a half of 2.sup.n namely, 2.sup.n-1 when m=2. In this event, when the relationship M&lt;2.sup.n-1 is kept in the plaintext M, the relationship C&lt;2.sup.n-1 is kept also in the ciphertext C at a high probability.
On the contrary, when the relationship M&gt;2.sup.n-1 is kept in the plaintext M, the relationship C&gt;2.sup.n-1 is kept also in the ciphertext C at a high probability, Accordingly, the value of the most significant bit of the plaintext M can be deduced from the value of the most significant bit of the ciphertext C. This problem can not be eliminated even with any transformation used as the transformation g and even when the transformation g is carried out between the transformation ELT and the transformation ELT.